import java.util.Arrays;

/**
* @description: 902. 最大为 N 的数字组合
* @author hewei
* @date 2022/8/15 16:26
* @version 1.0
*/

public class AtMostNGivenDigitSet {

    String[] digits;
    char[] chars;
    int[] dp;
    public int atMostNGivenDigitSet1(String[] digits, int n) {
        this.digits = digits;
        chars = Integer.toString(n).toCharArray();
        dp = new int[chars.length];
        Arrays.fill(dp, -1);
        return process(0, true, false);
    }

    public int process(int i, boolean isLimit, boolean isNum) {
        if (i == chars.length) return isNum ? 1 : 0;
        if (!isLimit && isNum && dp[i] >= 0) return dp[i];

        int res = 0;
        if (!isNum) res += process(i + 1, false, false);
        for (int j = 0, temp = isLimit ? chars[i] - '0' : 9; j < digits.length && Integer.parseInt(digits[j]) <= temp; j++) {
            res += process(i + 1, isLimit && Integer.parseInt(digits[j]) == temp, true);
        }
        if (!isLimit && isNum) dp[i] = res;
        return res;
    }

    public int atMostNGivenDigitSet(String[] digits, int n) {
        char[] chars = Integer.toString(n).toCharArray();
        int temp = digits.length;
        int[] dp = new int[chars.length + 1];
        dp[chars.length] = 1;
        for (int i = chars.length - 1; i >= 0; i--) {
            int c = chars[i] - '0';
            for (String digit : digits) {
                int a = Integer.parseInt(digit);
                if (a < c) {
                    dp[i] += Math.pow(temp, chars.length - 1 - i);
                } else if (a == c) {
                    dp[i] += dp[i + 1];
                }
            }
        }
        int ans = dp[0];
        for (int i = 1; i < chars.length; i++) {
            ans += Math.pow(temp, i);
        }
        return ans;
    }
}
